var arr = [3, 5, 7, 1, 4, 56, 12, 37, 78, 25, 0, 9, 3, 8, 42];

function heapSort(array) {
  creatHeap(array);
}
// 构建大顶堆，从第一个非叶子节点开始，进行下沉操作
function creatHeap(array) {
  const len = array.length;
  const start = parseInt(len / 2) - 1;
  for (let i = start; i >= 0; i--) {
    adjust(array, i, len);
  }
}
function adjust(array, target, len) {
  for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
    // 找到孩子节点中最大的
    if (i + 1 < len && array[i + 1] > array[i]) {
      i = i + 1;
    }
    // 下沉
    if (array[i] > array[target]) {
      [array[i], array[target]] = [array[target], array[i]];
      target = i;
    } else {
      break;
    }
  }
}
console.log(heapSort(arr));
